﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;

//顺时针打印矩阵
//https://www.nowcoder.com/questionTerminal/9b4c81a02cd34f76be2659fa0d54342a
//class Solution {
//public:
//    vector<int> printMatrix(vector<vector<int> > matrix) {
//        //确定起点坐标[0,0] 和终点坐标 [x,y]
//        int x1 = 0; //行
//        int y1 = 0; //列
//        int x2 = matrix.size() - 1; //行
//        int y2 = matrix[0].size() - 1; //列
//        vector<int> ret;
//        ret.reserve((x2 + 1) * (y2 + 1));
//        while (x1 <= x2 && y1 <= y2)
//        {
//            //第一行 x1,y1->y2
//            for (int i = y1; i <= y2; ++i)
//                ret.push_back(matrix[x1][i]);
//
//            //防止重复输入
//            if (x1 < x2)
//            {
//                //最后一列x1+1->x2,y2
//                for (int i = x1 + 1; i <= x2; ++i)
//                    ret.push_back(matrix[i][y2]);
//
//                //最后一行x2,y2-1->y1
//                for (int i = y2 - 1; i >= y1; --i)
//                    ret.push_back(matrix[x2][i]);
//            }
//
//            if (y1 < y2)
//            {
//                //第一列x2-1->x1+1,y1
//                for (int i = x2 - 1; i > x1; --i)
//                    ret.push_back(matrix[i][y1]);
//            }
//
//            ++x1; ++y1;
//            --x2; --y2;
//        }
//        return ret;
//    }
//};

//左右最值最大差
//https://www.nowcoder.com/questionTerminal/f5805cc389394cf69d89b29c0430ff27
//class MaxGap {
//public:
//    int findMaxGap(vector<int> A, int n) {
//        //两个特殊区间[0,0][1,n-1] | [0,n-2][n-1,n-1]
//        int maxn = 0;
//        for (const auto& x : A) maxn = max(x, maxn);
//
//        return maxn - min(A[0], A[n - 1]);
//    }
//};